//https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=23450&ru=%2Fpractice%2Ff836b2c43afc4b35ad6adc41ec941dba&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路：1.双指针移动next 指针+dumy空节点设置，next_next指针 ，如果next_next 与 next 一直相等，那么一直移动next_next，直到不相等时候，同时更新next与next_next；
//     2.使用哈希表或者是queue解决，需要遍历两次链表；
//     3.重点难题；

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <unordered_map>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        if (pHead->next == nullptr) return pHead;

        auto dumy_ptr = new ListNode(0);
        dumy_ptr ->next= pHead;
        auto cur = dumy_ptr;
        auto p1_next = dumy_ptr->next;
        auto p1_next_next = dumy_ptr->next->next;

        while (p1_next_next != nullptr) {
            if (p1_next->val == p1_next_next->val) {
                while(p1_next_next && p1_next->val == p1_next_next->val) {
                    auto dumplicate_node = p1_next_next;
                    p1_next_next = p1_next_next->next;
                    delete dumplicate_node;
                    
                }
                if (p1_next_next == nullptr) {
                    cur->next = nullptr;
                    break;
                }
                cur->next = p1_next_next;
                p1_next = p1_next_next;
                p1_next_next = p1_next->next;
            }
            else {
                cur = cur->next;
                p1_next = cur->next;
                p1_next_next = p1_next->next;
            }

        }
        auto res = dumy_ptr->next;
        delete dumy_ptr;
        return res; 
    }
};


#include <queue>
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        if (pHead->next == nullptr) return pHead;

        std::queue<ListNode*> queue;
        ListNode* cur=pHead,*res=nullptr;
        ListNode* next=pHead->next;
        while(cur){
            if(next!=nullptr&&cur->val!=next->val&&cur->next==next){
                queue.push(cur);
                next=next->next;
                cur=cur->next;
            }else if(next!=nullptr&&cur->val==next->val){
                next=next->next;
            }else if(next!=nullptr&& cur->val!=next->val &&cur->next!=next){
                cur=next;
                next=next->next;
            }else if(next==nullptr&&cur->next!=nullptr){
                break;
            }else if(next==nullptr&&cur->next==nullptr){
                queue.push(cur);
                break;
            }
        }
        if(queue.empty()) return res;
        ListNode*  first_node=queue.front();
        res=first_node;
        queue.pop();
        while(!queue.empty()){
            ListNode* cur_node=queue.front();
            queue.pop();
            first_node->next=cur_node;
            first_node=first_node->next;
        }
        return res; 
    }
};

class Solution2 {
  public:
    ListNode* deleteDuplication(ListNode* pHead) {
        //空链表
        if (pHead == NULL)
            return NULL;
        unordered_map<int, int> mp;
        ListNode* cur = pHead;
        //遍历链表统计每个节点值出现的次数
        while (cur != NULL) {
            mp[cur->val]++;
            cur = cur->next;
        }
        ListNode* res = new ListNode(0);
        ListNode* pre=res;
        //在链表前加一个表头
        cur = pHead;
        //再次遍历链表
        while (cur != NULL) {
            //如果节点值计数不为1
            if (mp[cur->val] != 1){
                //删去该节点
                ListNode* next_node =cur->next;
                delete cur;
                cur = next_node;
            }
            else{
                pre->next=cur;
                cur = cur->next;
                pre=pre->next;
                pre->next=nullptr;
            }  
        }
        return res->next;
    }
};

